open Graph

module StringBool = struct
    type t = string * bool
end

module G = Imperative.Graph.Abstract(StringBool)
module B = Builder.I(G)			
   
module DotInput = 
    Dot.Parse (B)
    (struct 
        let node (id,_) _ = 
		   match id with
	       | Dot_ast.Ident s
	       | Dot_ast.Number s
	       | Dot_ast.String s
	       | Dot_ast.Html s -> s,false
        let edge _ = ()
    end)	  
		  
module Display = struct
    include G
    let vertex_name v = fst (V.label v)
    let graph_attributes _ = []
    let default_vertex_attributes _ = []
    let vertex_attributes v = [`Label(if snd (G.V.label v) 
	                                  then "MIS Member" 
									  else (fst (G.V.label v)))]
    let default_edge_attributes _ = []
    let edge_attributes _ = []
    let get_subgraph _ = None
end

module DotOutput = Graphviz.Neato(Display)

open ISP
module IndSet = ISP(G)
open IndSet

let () =  
    try
        let input = DotInput.parse Sys.argv.(1) in
		(*find the largest independent set*)
		let startTime = Sys.time() in
		let maxIndSet = 
		    print_string ("Search started,");
            (List.map (fun v -> (G.V.label v)) (cliques (conversion input))) 
	    in
		let finishTime = Sys.time() in
		(*print result*)
		print_string "\n\nLargest MIS found: ";
        List.iter (fun v -> print_string ((fst v)^",")) maxIndSet;
		print_string "\n\nWriring file to result.dot,";
	    (*create a new vertices, (_,true) - MIS members*)
		let newVertices = G.fold_vertex 
                             (fun v vs -> 
                                 if (List.mem (G.V.label v) maxIndSet)
                                 then (G.V.create (fst (G.V.label v),true))::vs
                                 else v::vs) input []
        in
		(*new Graph without edges*)
        let vertexGraph = (List.fold_left (fun g v -> B.add_vertex g v) (B.empty ()) newVertices) in
        let newGraph = 
		    (*find vertex by name*)
		    let findVertex v = List.find (fun w -> (fst (G.V.label w)) == (fst (G.V.label v))) in          
		    G.fold_edges (fun v1 v2 g -> 
			    B.add_edge g (findVertex v1 newVertices) (findVertex v2 newVertices)) 
		    input vertexGraph
		in
	    let oc = open_out "result.dot" in			   
        DotOutput.output_graph oc newGraph;
	    close_out oc; 
		print_string "\n\nFinished. ";
		Printf.printf "\n\nAlgorithm execution time = %f." (finishTime -. startTime)
	with 
	    | Invalid_argument _ -> print_string "Please, specify the source file."
        | Sys_error s -> print_string s; 
        | Failure s -> print_string ("Source must be correct DOT file. "^s);
